An important element for providing advanced telecommunications services requiring large bandwidth is a high capacity packet switch capable of interconnecting a large number of input ports with a large number of output ports. A packet switch that can connect any specific input port to any specific output port is known as a full access packet switch.
Typically, such a packet switch is synchronous and the packets routed therein are of fixed length. During a packet switch cycle, packets present at the input ports are routed through an interconnect network comprising part of the packet switch to specific output ports. More particularly, if the interconnection network is self-routing, each packet arriving at an input port is provided with a header which contains the address of a specific output port to which the packet is to be routed. The interconnection network utilizes this address information to route the packets to the specific output ports.
A packet switch is internally non-blocking if it can deliver all packets from the input ports to the requested output ports when the packets are addressed to distinct output ports. However, there is still the possibility of external blocking, i.e. an internally non-blocking packet switch can still block if there are two simultaneous requests for the same output port. In this case, one or both packets directed to the same output port will be blocked or destroyed. Thus, a packet switch is desirably both internally and externally non-blocking.
One potential interconnection network for use in a packet switch is a digital sorting network developed by K.E. Batcher and disclosed in U.S. Pat. No. 3,428,946. Sorting involves rearranging an unordered sequence of numbers to create an ordered sequence of numbers. Basically, the Batcher sorting network comprises interconnected 2.times.2 switching nodes which can assume either a "pass-through" or a "cross" state. The decision as to which state a particular switching node assumes is determined by information contained in the headers of the packets present at the two inputs to the switching node. This characteristic of the switching nodes makes the Batcher network self-routing. Thus, packets arriving simultaneously at the inputs of a Batcher sorting network are sorted by the Batcher network so that they emerge in non-increasing or non-decreasing order according to an address contained in the packet header, which address, for example, corresponds to a destination address.
Batcher suggests in his patent that his sorting network may be used as a full access interconnection network because an input signal can, in effect, specify a connection to a particular output. The specified connections are made, according to Batcher, by numbering the outputs in order and presenting the number (i.e. the address) of a desired output as part of the input signal (e.g., as part of a packet header). The sorting network sorts the input signals so that each input signal emerges at the appropriate output as indicated by the output number or address contained therein.
Unfortunately, the Batcher sorting network, like all other sorting networks, has a serious drawback which prevents it from being used as an interconnection network for a full access packet switch. Specifically, the Batcher network fails to switch properly when there are inactive output ports (i.e. unsought destinations). Because a sorting network merely rearranges the order of the input signals and thus deals only with the positions of signals relative to the positions of other signals, the only time the Batcher network is sure to route input packets to the proper outputs is when each and every output port is the destination of one and only one input packet. These circumstances are generally not prevailing for packet switches used in actual telecommunications systems. In a typical packet switch cycle of a typical packet switch, there may be no packets addressed to certain output ports, while other output ports may have more than one packet addressed to them.
Accordingly, in order to use a sorting network such as the Batcher network as an interconnection network for a full access packet switch, it is necessary to account for unsought destinations and destinations sought by more than one packet. Solutions to the sorting network problems are presented in Huang et al., U.S. Pat. No. 4,516,238. In the Huang et al. patent, the appearance at the sorting network inputs of more than one packet addressed to a particular output is remedied by a trap network which is coupled to the outputs of the sorting network. The sorting network orders the packets in non-decreasing order according to destination (i.e. output) address and the trap network removes all but one packet seeking a particular destination. The occurrence of unsought destinations is remedied with a self-routing expander network located at the output of the trap network. Alternatively, a banyan network may be used for this purpose. Thus, in accordance with the disclosure of the Huang et al. patent, a full access, non-blocking, self-routing packet switch may be formed by utilizing a sorting network to sort input packets in non-decreasing order according to destination addresses contained in the packet headers, a trap network to remove all but one packet seeking each destination, and an expander network to route the remaining packets (i.e. those left by the trap network) to the destination addresses indicated in the packet headers.
It is an object of the present invention to provide a full access, non-blocking, self-routing packet switch utilizing a sorting network as an interconnection network without the use of a trap network and an expander or banyan network.